/**
 * 平衡二叉树 c与c++混合开发 c模式进行开发
 * 
 * */
#include <iostream>
#include <malloc.h>
using namespace std;

const int LEFT = 1;
const int RIGHT = -1;
const int MAX_LEFT = 2;
const int MAX_RIGHT = -2;
// int minLevel(tree_node *node);
typedef struct TreeNode
{
    int level=0;
    int data;
    TreeNode *left = 0;
    TreeNode *right = 0;
    TreeNode *parent = 0;
} tree_node;

typedef struct Tree{
    tree_node *root;
} tree1;

tree1 *tree = (tree1*)malloc(sizeof(tree1));

int getDepth(tree_node *node);
void left_left(tree_node* node);
void right_right(tree_node* node);
void rebuild(tree_node *node);

//插入一个数据
void insert(Tree *tree,int data){
    tree_node *new_node = (tree_node*)malloc(sizeof(tree_node));
    new_node->data = data;
    new_node->left=0;
    new_node->right=0;
    new_node->parent=0;
    if(tree->root==0){
        new_node->level = 0;
        tree->root = new_node;
        return;
    }

    tree_node *root = tree->root;
    tree_node *curr = tree->root;
    tree_node *tmp_parent;
    bool left = true;
    while (curr!=0)
    {
        tmp_parent = curr;
        if(curr->data>data){
            curr = curr->left;
            left = true;
        }else{
            curr = curr->right;
            left = false;
        }
    }

    new_node->level = tmp_parent->level+1;
    if(left)    {
        tmp_parent->left = new_node;
        new_node->parent = tmp_parent;
    }else{
        tmp_parent->right = new_node;
        new_node->parent = tmp_parent;
    }
    rebuild(new_node);
}

//步骤：1、按照二叉树插入数据；
//2、当插入数据时，判断该节点是否平衡，如果平衡，则判断其父节点是否平衡（右子树的高度与左子树的高度）。如果父节点为空，跳转至6；
//3、如果不平衡，则该节点为不平衡子树的根节点；
//4、调整树的平衡（LL,RR,LR,RL）；
//5、跳转至2；
//6、结束；
//记录叶子节点的最小深度 递归
int minLevel(tree_node *node){
    if (node==0){
        return 1;
    }
    int tmp_left = minLevel(node->left);
    cout<<"left-:"<<tmp_left<<endl;
    int tmp_right = minLevel(node->right);
    cout<<"right-:"<<tmp_right<<endl;
    return min(tmp_left,tmp_right)+1;
}
//balance factor,平衡因子=左子树的高度-右子树的高度
int bf(tree_node* node){
    return getDepth(node->left) - getDepth(node->right);
}
//获取树的最大深度
int getDepth(tree_node *node){
    if(node==0){
        return 0;
    }
    return 1+max(getDepth(node->left),getDepth(node->right));
}

void rebuild(tree_node *node){
    while (node!=0)
    {
        int balance_factor = bf(node);
        if(balance_factor==MAX_LEFT)
        {
            int bf2 = bf(node->left);
            if(bf2==LEFT){
                left_left(node);
            }else if(bf2 == RIGHT)
            {
                right_right(node->left);
                left_left(node);
            }
        }else if (balance_factor==MAX_RIGHT)
        {
            int bf2 = bf(node->right);
           if(bf2==LEFT){
                left_left(node->right);
                right_right(node);
            }else if(bf2 == RIGHT)
            {
                right_right(node->right);
            }
        }
        node = node->parent;
    }
    
}
//left_left
void right_right(tree_node* node){
    //围绕该点旋转
    tree_node* point_node = node->right;

    node->right = point_node->left;
    if(node->right != 0){
        point_node->left->parent = node;
        point_node->left=0;
    }
    point_node->parent = node->parent;
    if(node->parent==0){
        tree->root = point_node;
    }else if (node->parent->right == node)
    {
        node->parent->right = point_node;
    }else if (node->parent->left == node)
    {
        node->parent->left = point_node;
    }
    node->parent = point_node;
    point_node->left = node;
}

//right_right型，需要左旋
void left_left(tree_node* node){
    //围绕该点旋转
    tree_node* point_node = node->left;

    node->left = point_node->right;
    if(node->left != 0){
        point_node->right->parent = node;
        point_node->right=0;
    }
    point_node->parent = node->parent;
    if(node->parent==0){
        tree->root = point_node;
    }else if (node->parent->left == node)
    {
        node->parent->left = point_node;
    }else if (node->parent->right == node)
    {
        node->parent->right = point_node;
    }
    node->parent = point_node;
    point_node->right = node;
}

void print(tree_node *node){
    if(node!=0){
        print(node->left);
        cout<<node->data<<endl;
        print(node->right);
    }
    return;
}
int main(){
    // int arr[] = {5,4,3,2,1,7};
    int arr[] = {5,7,6};
    tree->root=0;
    for(int a: arr){
        insert(tree,a);
    }
    tree_node* node = tree->root;
    print(tree->root);
    cout<<endl;
}